﻿/* floodfill.cpp
 * 
 * Copyright (C) 2020, 2021 Yuan LI
 * email:18069211@qq.com
 * https://blog.csdn.net/liyuanbhu
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or (at
 * your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 */


#include "floodfill.h"
#include <QStack>

bool floodFill(QImage &image, QPoint seedPoint, uint32_t newVal )
{
    switch (image.format()) {
    case QImage::Format_Grayscale8:
        floodFill_Gray(image, seedPoint, static_cast<uchar>(newVal & 0xff));
        break;
    case QImage::Format_RGB32:
    case QImage::Format_ARGB32:
    case QImage::Format_RGBA8888:
    case QImage::Format_RGBX8888:
    case QImage::Format_ARGB32_Premultiplied:
    case QImage::Format_RGBA8888_Premultiplied:
        floodFill_RGB32(image, seedPoint, newVal);
        break;
    case QImage::Format_BGR888:
    case QImage::Format_RGB888:
        floodFill_RGB24(image, seedPoint, newVal );
        break;

    default:
        return false;
    }
    return false;
}

/**
 * @brief fillPoint_Gray 填充一个点。内部函数，不检查 image 的 format 是否正确。
 * @param image
 * @param p
 * @param val
 * @param newVal
 * @param stack
 * @return
 */
static inline bool fillPoint_Gray(QImage &image, QPoint p, uchar val, uchar newVal, QStack<QPoint> &stack)
{
    int x = p.x();
    int y = p.y();
    uchar *line = image.scanLine(y);
    if( line[x] != val )
    {
        return false;
    }
    line[x] = newVal;
    if( y > 0 )
    {
        const uchar *last = image.constScanLine(y - 1);
        if( last[x] == val )
        {
            stack.push(QPoint(x, y - 1));
        }
    }
    if( y < image.height() - 1 )
    {
        const uchar *next = image.constScanLine(y + 1);
        if( next[x] == val )
        {
            stack.push(QPoint(x, y + 1));
        }
    }
    return true;
}

static inline bool fillPoint_RGB32( QImage &image, QPoint p, uint32_t val, uint32_t newVal, QStack<QPoint> &stack )
{
    int x = p.x();
    int y = p.y();
    uint32_t *line = reinterpret_cast<uint32_t *> ( image.scanLine(y) );

    if( line[x] != val )
    {
        return false;
    }
    line[x] = newVal;
    if( y > 0 )
    {
        uint32_t *last = reinterpret_cast<uint32_t *> ( image.scanLine(y - 1) );
        if( last[x] == val )
        {
            stack.push(QPoint(x, y - 1));
        }
    }
    if( y < image.height() - 1 )
    {
        uint32_t *next = reinterpret_cast<uint32_t *> ( image.scanLine(y + 1) );
        if( next[x] == val )
        {
            stack.push(QPoint(x, y + 1));
        }
    }
    return true;
}

bool fillPoint_RGB24( QImage &image, QPoint p, uint32_t val, uint32_t newVal, QStack<QPoint> &stack)
{
    int x = p.x();
    int y = p.y();
    uchar *line = image.scanLine(y);
    uchar r = line[3 * x + 0];
    uchar g = line[3 * x + 1];
    uchar b = line[3 * x + 2];
    uint32_t color = (b << 16) + (g << 8) + r;
    if( color != val )
    {
        return false;
    }
    line[3 * x + 0] = (newVal >> 0) & 0xff;
    line[3 * x + 1] = (newVal >> 8) & 0xff;
    line[3 * x + 2] = (newVal >> 16) & 0xff;
    if( y > 0 )
    {

        uchar *last = image.scanLine(y - 1);
        r = last[3 * x + 0];
        g = last[3 * x + 1];
        b = last[3 * x + 2];
        color = (b << 16) + (g << 8) + r;
        if( color == val )
        {
            stack.push(QPoint(x, y - 1));
        }
    }
    if( y < image.height() - 1 )
    {
        uchar *next = image.scanLine(y + 1);
        r = next[3 * x + 0];
        g = next[3 * x + 1];
        b = next[3 * x + 2];
        color = (b << 16) + (g << 8) + r;
        if( color == val )
        {
            stack.push(QPoint(x, y + 1));
        }
    }
    return true;
}


static inline bool fillPoint_Gray( QImage &image, QPoint p, uchar low, uchar high, uchar newVal, QStack<QPoint> &stack)
{
    int x = p.rx();
    int y = p.ry();
    uchar *line = image.scanLine(y);
    if( line[x] < low || line[x] > high )
    {
        return false;
    }
    line[x] = newVal;
    if( y > 0 )
    {
        uchar *last = image.scanLine(y - 1);
        if( last[x] >= low && last[x] <= high )
        {
            stack.push(QPoint(x, y - 1));
        }
    }
    if( y < image.height() - 1 )
    {
        uchar *next = image.scanLine(y + 1);
        if( next[x] >= low && next[x] <= high )
        {
            stack.push(QPoint(x, y + 1));
        }
    }
    return true;
}

bool floodFill_Gray(QImage &image, QPoint seedPoint, uchar newVal )
{
    if(image.format() != QImage::Format_Grayscale8)
    {
        return false;
    }
    int width = image.width();
    int height = image.height();
    int x = seedPoint.x();
    int y = seedPoint.y();
    if(x < 0 || x >= width || y < 0 || y >= height)
    {
        return false;
    }
    int value = image.scanLine(y)[x];
    QStack<QPoint> stack;
    stack.push(seedPoint);

    while(!stack.isEmpty())
    {
        QPoint p = stack.pop();
        bool ret = fillPoint_Gray(image, p, value, newVal, stack);
        bool ret2 = ret;
        y = p.y();
        x = p.x();
        x--;
        while(x >= 0 && ret)
        {
            ret = fillPoint_Gray(image, QPoint(x, y), value, newVal, stack);
            x--;
        }

        x = p.x();
        x ++;
        while(x < width && ret2)
        {
            ret2 = fillPoint_Gray(image, QPoint(x, y), value, newVal, stack);
            x++;
        }
    }
    return true;
}

bool floodFill_Gray(QImage &image, QPoint seedPoint, uchar low, uchar high, uchar newVal )
{
    if(image.format() != QImage::Format_Grayscale8)
    {
        return false;
    }
    if(low > high)
    {
        return false;
    }

    QStack<QPoint> stack;
    stack.push(seedPoint);

    int width = image.width();
    while(!stack.isEmpty())
    {
        QPoint p = stack.pop();
        bool ret = fillPoint_Gray(image, p, low, high, newVal, stack);
        bool ret2 = ret;
        int y = p.y();
        int x = p.x();
        x--;
        while(x >= 0 && ret)
        {
            ret = fillPoint_Gray(image, QPoint(x, y), low, high, newVal, stack);
            x--;
        }

        x = p.x();
        x ++;
        while(x < width && ret2)
        {
            ret2 = fillPoint_Gray(image, QPoint(x, y), low, high, newVal, stack);
            x++;
        }
    }
    return true;
}

bool floodFill_RGB24(QImage &image, QPoint seedPoint, uint32_t newVal )
{
    switch (image.format()) {
    case QImage::Format_BGR888:
    case QImage::Format_RGB888:
        break;
    default:
        return false;
    }
    int width = image.width();
    int height = image.height();
    int x = seedPoint.x();
    int y = seedPoint.y();
    if(x < 0 || x >= width || y < 0 || y >= height)
    {
        return false;
    }
    const uchar *line = image.constScanLine(y);
    uchar r = line[3 * x + 0];
    uchar g = line[3 * x + 1];
    uchar b = line[3 * x + 2];
    uint32_t value = (b << 16) + (g << 8) + r;

    QStack<QPoint> stack;
    stack.push(seedPoint);

    while(!stack.isEmpty())
    {
        QPoint p = stack.pop();
        bool ret = fillPoint_RGB24(image, p, value, newVal, stack);
        bool ret2 = ret;
        y = p.y();
        x = p.x();
        x--;
        while(x >= 0 && ret)
        {
            ret = fillPoint_RGB24(image, QPoint(x, y), value, newVal, stack);
            x--;
        }

        x = p.x();
        x ++;
        while(x < width && ret2)
        {
            ret2 = fillPoint_RGB24(image, QPoint(x, y), value, newVal, stack);
            x++;
        }
    }
    return true;
}

bool floodFill_RGB32(QImage &image, QPoint seedPoint, uint32_t newVal )
{
    switch (image.format()) {
    case QImage::Format_RGBA8888:
    case QImage::Format_RGBX8888:
    case QImage::Format_RGBA8888_Premultiplied:
    case QImage::Format_ARGB32:
    case QImage::Format_RGB32:
    case QImage::Format_ARGB32_Premultiplied:
        break;
    default:
        return false;
    }
    int width = image.width();
    int height = image.height();
    int x = seedPoint.x();
    int y = seedPoint.y();
    if(x < 0 || x >= width || y < 0 || y >= height)
    {
        return false;
    }

    const uint32_t *line = reinterpret_cast<const uint32_t *> ( image.constScanLine(y) );
    uint32_t value = line[x];

    QStack<QPoint> stack;
    stack.push(seedPoint);

    while(!stack.isEmpty())
    {
        QPoint p = stack.pop();
        bool ret = fillPoint_RGB32(image, p, value, newVal, stack);
        bool ret2 = ret;
        y = p.y();
        x = p.x();
        x--;
        while(x >= 0 && ret)
        {
            ret = fillPoint_RGB32(image, QPoint(x, y), value, newVal, stack);
            x--;
        }

        x = p.x();
        x ++;
        while(x < width && ret2)
        {
            ret2 = fillPoint_RGB32(image, QPoint(x, y), value, newVal, stack);
            x++;
        }
    }
    return true;
}
